#include <iostream>
#include "euler.h"

BEGIN_PROBLEM(169, solve_problem_169)
	PROBLEM_TITLE("Express a number as a sum of powers of 2")
	PROBLEM_ANSWER("178653872807")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("log(n)")
	PROBLEM_SPACE_COMPLEXITY("log(n)")
END_PROBLEM()

// Computes a*f(k) + b*f(k-1)
static long long g(long long a, long long b, long long k)
{
	if (k == 1)
		return a + b;
	else if (k % 2 == 0)
		return g(a, a+b, k/2);
	else
		return g(a+b, b, k/2);
}

static long long f(long long n)
{
	if (n < 0)
		return 0;
	else if (n == 0)
		return 1;
	else if (n % 2 == 1)
		return f((n - 1) / 2);
	else
		// return f(n / 2) + f((n - 2) / 2);
		return g(1, 1, n / 2);
}

static void solve_problem_169()
{
	bool verbose = false;

	if (verbose)
	{
		for (long long i = 0, x = 1; i < 19; i++, x *= 10)
		{
			std::cout << "f(10^" << i << ") = " << f(x) << std::endl;
		}
	}

	std::cout << g(1, 25, 3125LL*3125LL*3125LL*3125LL*3125LL) << std::endl;
}
